package br.edu.ufcg.splab.simulator.clique;

import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

import br.edu.ufcg.splab.simulator.clique.graph.UndirectedGraph;
import br.edu.ufcg.splab.simulator.clique.graph.Vertex;

public class Clique {
	private UndirectedGraph graph;
	private Map<Integer, Vertex> vertexMap;

	private Set<Set<Vertex>> cliques;

	public Clique(UndirectedGraph graph){
		this.graph = graph;
		cliques = new HashSet<Set<Vertex>>();
		
		List<Vertex> vertices = graph.getVertices();
		vertexMap = new HashMap<Integer, Vertex>(graph.getVertexCount());
		int i = 1;
		for (Vertex v : vertices) {
			vertexMap.put(i++, v);
		}
	}
	
	/**
	 * Returns the complete subgraphs ("cliques") in the graph, i.e., sets of elements where each pair of elements is connected.
	 * @return The cliques in a graph.
	 */
	public Set<Set<Vertex>> getCliques() {
		cliques.clear();
		findCompleteSubgraphs(new HashSet<Vertex>(), 1);
		removeCopies();
		return cliques;
	}

	/** 
	 * Method that finding the cliques in the graph for a specific vertex.
	 * @param vertexCliques The cliques of the vertex.
	 * @param vertexIndex The vertex using as base to find their cliques.
	 */
	private void findCompleteSubgraphs(Set<Vertex> vertexCliques, Integer vertexIndex) {
		if(vertexIndex <= graph.getVertexCount()){
			Vertex vertex = vertexMap.get(vertexIndex);
			Set<Vertex> neighbors = graph.getNeighbors(vertex);
			if (neighbors.containsAll(vertexCliques)) {
				findCompleteSubgraphs(addVertexInClique(vertexCliques, vertex), vertexIndex + 1);
			} else {
				findCompleteSubgraphs(cloneClique(vertexCliques), vertexIndex + 1);
				Set<Vertex> intersection = intersection(neighbors, vertexCliques);
				Set<Vertex> lexiClique = getLexicographicSmallestMaximalClique(intersection, vertexIndex - 1);
				if (vertexCliques.equals(lexiClique)) {
					findCompleteSubgraphs(addVertexInClique(intersection, vertex), vertexIndex + 1);
				}
			}
		}else{		
			cliques.add(vertexCliques);
		}
	}

	/**
	 * Creates a copy of a clique and adds a vertex in this cloned clique.
	 * 
	 * @param clique The clique to be cloned.
	 * @param vertex The vertex to be added in this clique.
	 * @return The copy of the clique with a new vertex added.
	 */
	private Set<Vertex> addVertexInClique(Set<Vertex> clique, Vertex vertex) {
		HashSet<Vertex> clone = new HashSet<Vertex>(clique);
		clone.add(vertex);
		return clone;
	}

	/**
	 * Creates and returns a copy of a clique.
	 * 
	 * @param clique The clique to be cloned.
	 * @return The copy of the clique.
	 */
	private Set<Vertex> cloneClique(Set<Vertex> clique) {
		return new HashSet<Vertex>(clique);
	}

	/**
	 * Returns the intersection of two cliques, i.e., the set containing only the elements common to both sets.
	 * 
	 * @return The intersection of two cliques.
	 */
	private Set<Vertex> intersection(Set<Vertex> clique1, Set<Vertex> clique2) {
		Set<Vertex> cloneSet = cloneClique(clique1);
		cloneSet.retainAll(clique2);
		return cloneSet;
	}

	/**
	 * Returns the smallest maximal clique in lexicographic order.
	 * 
	 * @return The smallest maximal clique in lexicographic order.
	 */
	private Set<Vertex> getLexicographicSmallestMaximalClique(Set<Vertex> clique, Integer maxIndex) {
		Set<Vertex> maximalClique = cloneClique(clique);
		for (int i = 1; i <= maxIndex; ++i) {
			Vertex node = vertexMap.get(i);
			Set<Vertex> neighbors = graph.getNeighbors(node);
			if (neighbors.containsAll(maximalClique))
				maximalClique.add(node);
		}
		return maximalClique;
	}
	
	/**
	 * Removes from the smallest cliques that are contained in the biggest cliques. 
	 */
	private void removeCopies(){
		Set<Set<Vertex>> remove = new HashSet<Set<Vertex>>();
		for(Set<Vertex> set : cliques){
			if(set.isEmpty()){
				remove.add(set);	
			}else{
				for(Set<Vertex> set2 : cliques){
					
					if(!set2.equals(set)){
						if(set2.containsAll(set)){
							remove.add(set);						
						}
					}
				}
			}
		}		
		for(Set<Vertex> set : remove){
			cliques.remove(set);
		}
	}

}
